{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fb4fd802",
   "metadata": {},
   "source": [
    "# 机器读心术之文本挖掘与自然语言处理第8课书面作业\n",
    "学号：207402\n",
    "\n",
    "**作业内容：**  \n",
    "1. 研究准确率，召回率指标的定义，说明为什么提高其中一项指标可能会降低另一项？  \n",
    "2. 设计一种面向中英文混排文本（即大量中文中夹杂少量英语单词）的分词方法，用语言描述即可，无需编程实现  \n",
    "3. 假设语料为："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80170df0",
   "metadata": {},
   "source": [
    "$$\n",
    "\\overset{B}{研}\\overset{E}{究}\\overset{B}{生}\\overset{E}{物}\\overset{S}{很}\\overset{S}{有}\\overset{B}{意}\\overset{E}{思}\\\\\n",
    "\\overset{S}{他}\\overset{B}{大}\\overset{E}{学}\\overset{B}{时}\\overset{E}{代}\\overset{S}{是}\\overset{B}{研}\\overset{E}{究}\\overset{B}{生}\\overset{E}{物}\\overset{S}{的} \\\\\n",
    "\\overset{B}{生}\\overset{E}{物}\\overset{B}{专}\\overset{E}{业}\\overset{S}{是}\\overset{S}{他}\\overset{S}{的}\\overset{B}{首}\\overset{E}{选}\\overset{B}{目}\\overset{E}{标} \\\\\n",
    "\\overset{S}{他}\\overset{S}{是}\\overset{B}{研}\\overset{M}{究}\\overset{E}{生} \\\\\n",
    "$$\n",
    "按照“基于字的生成式和判别式模型相结合的分词方法”（宗成庆书第145页），判断句子“他 是 研究 生物 的”和“他 是 研究生 物 的”哪个分词更加合理，手算或程序计算均可"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72934a67",
   "metadata": {},
   "source": [
    "## 第1题"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e4b7ab9",
   "metadata": {},
   "source": [
    "宗成庆书中对于准确率与召回率定义如下："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc50a653",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "准确率=\\frac{正确识别的实体数}{总的识别实体数}\\times 100\\% \\\\\n",
    "召回率=\\frac{正确识别的实体数}{总的实体数}\\times 100\\%\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5debd792",
   "metadata": {},
   "source": [
    "解释准确率与召回率的关系，可以参见周志华书对此的说明：\n",
    "\n",
    "|                    | 预测为正例   | 预测为反例   |\n",
    "| ------------------ | ------------ | ------------ |\n",
    "| **真实情况为正例** | TP（真正例） | FN（假反例） |\n",
    "| **真实情况为反例** | FP（假正例） | TN（真反例） |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "445558ff",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "P(Precision, 准确率/查准率)=\\frac{TP}{TP+FP} \\\\\n",
    "R(Recall, 召回率/查全率)=\\frac{TP}{TP+FN}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a83f211",
   "metadata": {},
   "source": [
    "准确率含义是“**在所有被预测为正的样本中实际为正的样本概率**”，召回率含义是“**在实际为正的样本中被预测为正样本的概率**”。如果只是一味追求准确率，会导致FN增加，会导致召回率降低。两者的关系可以体现为P-R图：\n",
    "![PR](https://gitee.com/dotzhen/cloud-notes/raw/master/PR.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea48393f",
   "metadata": {},
   "source": [
    "## 第2题"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edcd1081",
   "metadata": {},
   "source": [
    "我们要设计的分词系统是要求：\n",
    "* 中英文混排；  \n",
    "* 但是是大量中文中夹杂少量英文单词。  \n",
    "这说明我们要设计的分词系统主要还是面向中文的。对于其中出现的英文，我打算采用如下方法来实现：  \n",
    "* 内置一个英文词典，构筑一个有限自动机来识别英文单词，这个相当于英文的已登录词识别；  \n",
    "* 先进行文本解析，如果读到有字母出现，就调用上文的有限自动机，如果能够识别，就将识别结果整体作为一个“汉字”来处理。  \n",
    "* 对于未在内置英文词典收录的字母组合，即未分录英文词，将其统一用一个特别的“汉字”来处理。  \n",
    "如下图所示："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d23fc093",
   "metadata": {},
   "source": [
    "![中英混排分词](https://gitee.com/dotzhen/cloud-notes/raw/master/%E4%B8%AD%E8%8B%B1%E6%B7%B7%E6%8E%92%E5%88%86%E8%AF%8D.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b90edd4",
   "metadata": {},
   "source": [
    "对于中文的分词在本次课程中结合宗成庆书已经提到了5种方法，我打算采用基于条件随机场的方式来做。这里就不过多说明了。  \n",
    "针对上图的所示：\n",
    "实际是对如果汉字做标记（标记可以采用BMES）：  \n",
    "我想知道[about]的意思  \n",
    "识别后的结果，应该是：  \n",
    "$$\n",
    "\\overset{S}{我}\\overset{S}{想}\\overset{B}{知}\\overset{E}{道}\\overset{S}{[about]}\\overset{S}{的}\\overset{B}{意}\\overset{E}{思}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a5e2658",
   "metadata": {},
   "source": [
    "## 第3题"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a8d3868",
   "metadata": {},
   "source": [
    "根据宗成庆书中**7.2.5**基于字的生成式模型和区分式模型相结合的汉语分词方法章节，最终是比较不同“字-标记”在语言模型中的出现概率，选择概率较大者即可，概率计算基于书中公式(7-13):"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06455974",
   "metadata": {},
   "source": [
    "$$\n",
    "P([c,t]_1^n)\\approx \\prod_{i=1}^n P([c,t]_i \\; |\\; [c,t]_{i-k}^{i-1}) \\tag{7-13}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71c35788",
   "metadata": {},
   "source": [
    "基于三元语言模式，上式中$k=2$:\n",
    "$$\n",
    "P([c,t]_1^n)\\approx \\prod_{i=1}^n P([c,t]_i \\; |\\; [c,t]_{i-2}^{i-1})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f47ab369",
   "metadata": {},
   "source": [
    "句子A：“他 是 研究 生物 的”可标记为：\n",
    "$$\n",
    "\\overset{S}{他}\\overset{S}{是}\\overset{B}{研}\\overset{E}{究}\\overset{B}{生}\\overset{E}{物}\\overset{S}{的}\n",
    "$$\n",
    "句子B：“他 是 研究生 物 的”可标记为：\n",
    "$$\n",
    "\\overset{S}{他}\\overset{S}{是}\\overset{B}{研}\\overset{M}{究}\\overset{E}{生}\\overset{S}{物}\\overset{S}{的}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6509fe7",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "P_A([c,t]_1^7)&\\approx P(\\overset{S}{他}|[start])P(\\overset{S}{是}|[start]\\overset{S}{他})P(\\overset{B}{研}|\\overset{S}{他}\\overset{S}{是})P(\\overset{E}{究}|\\overset{S}{是}\\overset{B}{研})P(\\overset{B}{生}|\\overset{B}{研}\\overset{E}{究})P(\\overset{E}{物}|\\overset{E}{究}\\overset{B}{生})P(\\overset{S}{的}|\\overset{B}{生}\\overset{E}{物}) \\\\\n",
    "&=\\frac{1}{2} \\times \\frac{1}{2} \\times \\frac{1}{1} \\times \\frac{1}{2} \\times \\frac{2}{2} \\times \\frac{2}{2} \\times \\frac{1}{3} \\\\\n",
    "&=\\frac{1}{24}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9603cf17",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "P_B([c,t]_1^7)&\\approx P(\\overset{S}{他}|[start])P(\\overset{S}{是}|[start]\\overset{S}{他})P(\\overset{B}{研}|\\overset{S}{他}\\overset{S}{是})P(\\overset{M}{究}|\\overset{S}{是}\\overset{B}{研})P(\\overset{E}{生}|\\overset{B}{研}\\overset{M}{究})P(\\overset{S}{物}|\\overset{M}{究}\\overset{E}{生})P(\\overset{S}{的}|\\overset{E}{生}\\overset{S}{物}) \\\\\n",
    "&=\\frac{1}{2} \\times \\frac{1}{2} \\times \\frac{1}{1} \\times \\frac{1}{2} \\times \\frac{1}{1} \\times \\frac{0}{1} \\times \\frac{0}{0} \\\\\n",
    "&=0\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e85ad113",
   "metadata": {},
   "source": [
    "从上面看$P_B$用极大似然估计会出现部分概率项为0的情况，导致$P_B$为0，对于这块我们可以采用JM平滑方法。  \n",
    "下面采用三阶JM方法来平滑计算，代码实现如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "8d44614e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "他 S ## ## 0.32122093023255816\n",
      "是 S #他 #S 0.34205426356589147\n",
      "研 B 他是 SS 0.6753875968992248\n",
      "究 E 是研 SB 0.42393410852713176\n",
      "生 B 研究 BE 0.7601744186046512\n",
      "物 E 究生 EB 0.7587209302325582\n",
      "的 S 生物 BE 0.2558139534883721\n",
      "P_A: 0.0046416226359046195\n",
      "\n",
      "他 S ## ## 0.32122093023255816\n",
      "是 S #他 #S 0.34205426356589147\n",
      "研 B 他是 SS 0.6753875968992248\n",
      "究 M 是研 SB 0.3391472868217054\n",
      "生 E 研究 BM 0.7572674418604651\n",
      "物 S 究生 ME 0.00436046511627907\n",
      "的 S 生物 ES 0.005813953488372093\n",
      "P_B: 4.831632857831908e-07\n"
     ]
    }
   ],
   "source": [
    "corpus=['研究生物很有意思','他大学时代是研究生物的','生物专业是他的首选目标','他是研究生']\n",
    "markers=['BEBESSBE','SBEBESBEBES','BEBESSSBEBE','SSBME']\n",
    "\n",
    "def mix_seq(chars, markers):\n",
    "    s=''\n",
    "    for j in range(len(chars)):\n",
    "       s+=chars[j]+markers[j]\n",
    "    return s\n",
    "\n",
    "def preprocess(corpus,markers):\n",
    "    querydb=[]\n",
    "    for i in range(len(corpus)):\n",
    "        s=mix_seq(corpus[i],markers[i])\n",
    "        querydb.append('####'+s) #为了处理简单在开头添加两个##,两个##对应的标记为##，所以这里有4个#\n",
    "    return querydb\n",
    "\n",
    "def calc_prob(target_char, target_marker, pre_chars, pre_markers, querydb):\n",
    "    t=0\n",
    "    c=0\n",
    "    if len(target_char)==len(target_marker):\n",
    "        target_search=mix_seq(target_char,target_marker)\n",
    "    else:\n",
    "        target_search=target_char\n",
    "    \n",
    "    if len(pre_chars) == 0:\n",
    "        for dbi in querydb:\n",
    "            t+=dbi.count(target_search)\n",
    "            c+=len(dbi)\n",
    "    else:\n",
    "        pre_search=mix_seq(pre_chars, pre_markers)\n",
    "        pre_target_search=pre_search+target_search\n",
    "        for dbi in querydb:\n",
    "            c+=dbi.count(pre_search)\n",
    "            t+=dbi.count(pre_target_search)\n",
    "    if c==0:\n",
    "        return 0.\n",
    "    else:\n",
    "        return t/c\n",
    "\n",
    "def calc_JM_proc(target_char, target_marker, pre_chars, pre_markers, querydb, lambda1):\n",
    "#     print(target_char, target_marker, pre_chars, pre_markers)\n",
    "    n= len(pre_chars)\n",
    "    if n == 0:\n",
    "        t1=calc_prob(target_char, target_marker, pre_chars, pre_markers, querydb)\n",
    "        t2=calc_prob(target_char, '','','',querydb)\n",
    "        p=lambda1*t1+(1-lambda1)*t2\n",
    "        return p\n",
    "    else:\n",
    "        t1=calc_prob(target_char, target_marker, pre_chars, pre_markers, querydb)\n",
    "        t2=calc_JM_proc(target_char, target_marker, pre_chars[1:], pre_markers[1:], querydb,lambda1)\n",
    "        p=lambda1*t1+(1-lambda1)*t2\n",
    "        return p\n",
    "\n",
    "def calc_sentence(sentence, markers,db):\n",
    "    p=1.0\n",
    "    t = 0.0\n",
    "    s='##'+sentence\n",
    "    m='##'+markers\n",
    "    for i in range(2,len(s)):\n",
    "        t=calc_JM_proc(s[i],m[i],s[i-2:i],m[i-2:i],db,0.5)\n",
    "        print(s[i],m[i],s[i-2:i],m[i-2:i],t)\n",
    "        p*=t\n",
    "    return p\n",
    "\n",
    "db = preprocess(corpus,markers)\n",
    "\n",
    "print('P_A:',calc_sentence('他是研究生物的','SSBEBES',db))\n",
    "print()\n",
    "print('P_B:',calc_sentence('他是研究生物的','SSBMESS',db))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38cd54cb",
   "metadata": {},
   "source": [
    "从计算结果看，显然句子A：“他 是 研究 生物 的”概率更大，是更合理的选择。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
